package algorithm.sort;

import java.io.IOException;

/**
 * 选择排序
 * 时间复杂度		O(n^2)
 * 选择排序是一种不稳定的排序算法
 * 
 * 优化思路：选择排序的优化思路一般是在一趟遍历中，同时找出最大值与最小值，放到数组两端，这样就能将遍历的趟数减少一半
 * 
 * 适用场景：待排序序列中，元素个数较少时
 * */
public class SelectionSort {
	public static void sort(int[] arr) {
		for(int i = 0; i < arr.length - 1; i++) {
			int k = i;
			for(int j = i + 1; j < arr.length; j++)
				if(arr[k] > arr[j])
					k = j;
			if(k != i)
				Swap.swap(arr, i, k);
		}
	}
	
	public static void sortOptimize(int[] arr) {		// 优化
		for(int left = 0, right = arr.length - 1; left <= right; left++, right--) {
			int k_min = left, k_max = right;
			for(int k = left; k <= right; k++) {
				if(arr[k] < arr[k_min])
					k_min = k;
				if(arr[k] > arr[k_max])
					k_max = k;
			}
			if(k_min != left)
				Swap.swap(arr, left, k_min);
			if(k_max == left)		// 最大值可能在上一次序列的最小值位置
				k_max = k_min;
			if(k_max != right)
				Swap.swap(arr, k_max, right);
		}
	}
	
	public static void main(String[] args) throws IOException {
		int[] arr = InputSequence.inputIntArray();
//		SelectionSort.sort(arr);
		SelectionSort.sortOptimize(arr);
		for(int i = 0; i < arr.length; i++)
            System.out.print(arr[i] + " ");
	}
}
